satisfiability problem

A problem used as an example in complexity theory. It can

be stated thus:

Given a Boolean expression E, decide if there is some

assignment to the variables in E such that E is true.

A Boolean expression is composed of Boolean variables,

(logical) negation (NOT), (logical) conjunction (AND) and

parentheses for grouping. The satisfiability problem was the

first problem to be proved to be NP-complete (by Cook).

["Introduction to Automata Theory, Languages, and Computation"

by Hopcroft and Ullman, pub. Addison-Wesley].

(1994-11-11)